package leetcode53;

/**
 * 「动态规划」的解法，我们先告诉大家，理解题意非常重要。其次，我们在做「动态规划」的问题的时候，需要经常思考 为什么想到需要这样定义状态。
 * 这是一道典型的使用「动态规划」解决的问题，需要我们掌握动态规划问题设计状态的技巧（无后效性），并且需要知道如何推导状态转移方程，最后再去优化空间。
 */
public class Solution3 {

    public int maxSubArray(int[] nums) {
        int len = nums.length;
        // dp[i] 表示：以 nums[i] 结尾的连续子数组的最大和
        int[] dp = new int[len];
        dp[0] = nums[0];

        for (int i = 1; i < len; i++) {
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
        }

        // 也可以在上面遍历的同时求出 res 的最大值，这里我们为了语义清晰分开写，大家可以自行选择
        int res = dp[0];
        for (int i = 1; i < len; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    public int maxSubArray1(int[] nums) {
        int[] dp2 = new int[nums.length];
        dp2[0] = nums[0];
        int max = dp2[0];
        for(int i=1;i < nums.length;i++){
            dp2[i] = Math.max(dp2[i-1] + nums[i],nums[i]);
            max = Math.max(max,dp2[i]);
        }
        return max;
    }
}